/* 
    求一个数组的逆序对：左边的数如果比右边大，则两个数构成一个逆序对，请打印所有逆序对。
    并归排序排序时，当左边不为空，从右边拿一个数，就应该存在产生（左边剩余元素个数）个逆序对。
*/
let reverseOrderPair = function (arr) {
    if (arr.length <= 1) {
        return arr;
    }
    let mid = Math.floor(arr.length / 2);
    let left = arr.slice(0, mid);
    let right = arr.slice(mid);
    return merge(reverseOrderPair(left), reverseOrderPair(right));
};

function merge(leftArr, rightArr) {
    let helpArr = [];
    while (leftArr.length && rightArr.length) {
        if (leftArr[0] > rightArr[0]) {
            let temp = rightArr.shift();
            leftArr.forEach((element) => {
                console.log([element, temp]);
            });
            helpArr.push(temp);
        } else {
            helpArr.push(leftArr.shift());
        }
    }
    if (leftArr.length) {
        leftArr.forEach((element) => {
            helpArr.push(element);
        });
    } else if (rightArr.length) {
        rightArr.forEach((element) => {
            helpArr.push(element);
        });
    }
    return helpArr;
}

let arr = [5, 9, 6, 1];
let res = reverseOrderPair(arr);
console.log(res);
